package com.atguigu.map;

public class BSTMap<K extends Comparable<K>,V> implements Map<K,V> {

    private class Node{
        public K key;
        public V value;
        public Node right;
        public Node left;
        public Node(K key,V value,Node left,Node right){
            this.key=key;
            this.value=value;
            this.right=right;
            this.left=left;
        }
        public Node(K key,V value){
            this(key,value,null,null);
        }

        @Override
        public String toString() {
            return "{"+key.toString()+" : "+value.toString()+"}";
        }
    }
    private Node root;
    private int size;
    public BSTMap(){
        root=null;
        size=0;
    }


    @Override
    //向二分搜索树中添加新的元素
    public void add(K key, V value) {
        root=add(root,key,value);
    }
    //向以root为根的二分搜索树中插入元素(key,value)
    //返回插入新节点后二分搜索树的根
    private Node add(Node root,K key,V value){
        if(root==null){
            size++;
            return new Node(key,value);
        }
        if(key.compareTo(root.key)<0){
            root.left=add(root.left,key,value);
        }else if(key.compareTo(root.key)>0){
            root.right=add(root.right,key,value);
        }else{//key.compareTo(root.key)==0
            root.value=value;
        }
        return root;
    }
    //返回以node为根节点的二分搜索树中，key所在的节点
    private Node getNode(Node root,K key){
        if(root==null){
            return null;
        }
        if(root.key.compareTo(key)>0){
            return getNode(root.left,key);
        }else if(root.key.compareTo(key)<0){
            return getNode(root.right,key);
        }else{
            return root;
        }
    }
    private Node minimum(Node root){
        if(root.left==null){
            return root;
        }
        return minimum(root.left);
    }
    private Node removeMin(Node root){
        if(root.left==null){
            Node rightNode=root.right;
            root.right=null;
            size--;
            return rightNode;
        }
        root.left=removeMin(root.left);
        return root;
    }
    @Override
    //从二分搜索树中删除Key节点
    public V remove(K key) {
        Node node=getNode(root,key);
        if(node!=null){
            root=remove(root,key);
            return node.value;
        }
        return null;
    }
    private Node remove(Node root,K key){
        if(root==null){
            return null;
        }
        if(key.compareTo(root.key)<0){
            root.left=remove(root.left,key);
        }else if(key.compareTo(root.key)>0){
            root.right=remove(root.right,key);
        }else{
            if(root.left==null){
                Node rightNode=root.right;
                size--;
                root.right=null;
                return rightNode;
            }
            if(root.right==null){
                Node leftNode=root.left;
                root.left=null;
                size--;
                return leftNode;
            }
            Node successor=minimum(root.right);
            successor.right=removeMin(root.right);
            successor.left=root.left;
            root.left=root.right=null;
            return successor;
        }
        return root;
    }

    @Override
    public boolean contains(K key) {
        return getNode(root,key)!=null;
    }

    @Override
    public V get(K key) {
        Node cur=getNode(root,key);
        return cur==null?null:cur.value;
    }

    @Override
    public void set(K key, V newValue) {
        Node cur=getNode(root,key);
        if(cur!=null){
            cur.value=newValue;
        }else{
            throw new IllegalArgumentException(key+" does't exist!");
        }
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }
}
